<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>
<body>
    <script>
        /* 
            题目描述： 给出不同面额的硬币以及一个总金额. 
            写一个方法来计算给出的总金额可以换取的最少的硬币数量. 
            如果已有硬币的任意组合均无法与总金额面额相等, 那么返回 -1.
        */
        /* 
            分析：假设现在硬币种类 1 3 5
            1.求最后一步
            拼出11的最少硬币数 f(11)= min(f(11 - 1),f(11 - 3),f(11 - 5)) + 1，同理后面也是这样求最少
            2.转移方程:n表示拼出n元的最少硬币数
            f(n) = i:0->coins.length (min(f(n - coins[i]))) + 1
            3.边界
                n - coins[i] > 0 进行计算
                f(0) = 0
                初始化全为-1
            4.计算顺序
             0 -> n
        */
       function ChargeMin(coins, amount){
           // 初始化状态
           let f = new Array(amount + 1).fill(Number.MAX_VALUE)
           f[0] = 0
           // 转移方程
           for(let i = 1; i <= amount; i++){
               let min = Number.MAX_VALUE
               for(let j = 0; j < coins.length; j++){
                //    钱数为正数，且能拼出来
                   if(i - coins[j] >= 0 && f[i - coins[j]] != Number.MAX_VALUE){
                        if(min > f[i - coins[j]]) min = f[i - coins[j]]
                   }
               }
               f[i] = min + 1
           }
           return f[amount] === Number.MAX_VALUE ? -1 :f[amount]
       }
       let coins = [1,3,5]
       let amount = 11
       console.log(ChargeMin(coins,amount))
    //    思路二： 可以简化状态方程 f(n) = min (f(n), f(n - coin[i]) + 1) 初始化设置f(n) = max
    </script>
</body>
</html>